// 文件名：queue_bfs_level_order.cpp
// 目的：使用 std::queue 实现图的广度优先搜索（BFS），按层序输出遍历顺序。
// 要点：
//   - Graph：unordered_map<string, vector<string>> 作为邻接表，查找均摊 O(1)；
//   - 访问集 visited：unordered_set，防重复入队；
//   - 队列 q：FIFO 保证层序遍历；
//   - contains(start) 先检查起点是否存在，避免非法访问；
//   - 遍历时对每个邻居执行 visited.insert(neighbor).second 判重后入队。
// 复杂度：时间 O(V+E)（均摊哈希），空间 O(V)（队列与访问集）。
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using Graph = std::unordered_map<std::string, std::vector<std::string>>;

void bfs(const Graph& graph, const std::string& start) {
    if (!graph.contains(start)) {
        std::cout << "Start node not found.\n";
        return;
    }

    std::unordered_set<std::string> visited;
    std::queue<std::string> q;

    visited.insert(start);
    q.push(start);

    std::cout << "BFS order: ";
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        std::cout << node << ' ';

        if (auto it = graph.find(node); it != graph.end()) {
            for (const auto& neighbor : it->second) {
                if (visited.insert(neighbor).second) {
                    q.push(neighbor);
                }
            }
        }
    }
    std::cout << '\n';
}

int main() {
    Graph graph = {
        {"A", {"B", "C"}},
        {"B", {"D", "E"}},
        {"C", {"F"}},
        {"E", {"F"}}
    };

    bfs(graph, "A");
    bfs(graph, "Z");
    return 0;
}